package com.stanley.alogrithm.sorts;

public class QuickSort {

    public static void main(String[] args) {

    }

    public static void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int pivotIndex = partition(array, begin, end);
        quickSort(array, begin, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, end);
    }

    private static int partition(int[] array, int begin, int end) {
        int pivot = array[end];
        int left = begin;
        int right = end - 1;
        System.out.println(String.format("before: left=%d, right=%d, end=%d", left, right, end));
        while (left <= right) {
            while (left <= right && array[left] <= pivot) {
                left++;
            }
            while (left <= right && array[right] > pivot) {
                right--;
            }
            if (left < right) {
                SortUtils.swap(array, left, right);
            }
        }
        if (array[left] > array[end]) {
            SortUtils.swap(array, left, end);
        }
        System.out.println(String.format("after: left=%d, right=%d, end=%d", left, right, end));
        return left;
    }

}
